﻿#include <iostream>
#include <stdexcept> // 用于异常处理

template <typename T>  // 声明模板参数T，类似 c# 泛型
class ArrayStack {
private:
    T* data;        // 存储栈元素的数组
    int capacity;   // 栈的容量
    int topIndex;   // 栈顶指针(索引)

public:
    // 构造函数
    ArrayStack(int cap = 10) : capacity(cap), topIndex(-1) {
        data = new T[capacity];
    }
     
    // 析构函数  负责释放动态分配的内存资源，防止内存泄漏
    ~ArrayStack() {
        delete[] data;
    }

    // 压栈操作
    void push(const T& value) {
        if (topIndex == capacity - 1) {
            resize(capacity * 2); // 如果栈满，扩容
        }
        data[++topIndex] = value;
    }

    // 弹栈操作
    T pop() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        T value = data[topIndex--];

        // 如果元素数量小于容量的1/4，缩小数组
        if (topIndex < capacity / 4 && capacity > 10) {
            resize(capacity / 2);
        }

        return value;
    }

    // 查看栈顶元素
    T top() const {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        return data[topIndex];
    }

    // 判断栈是否为空
    bool isEmpty() const {
        return topIndex == -1;
    }

    // 获取栈的大小
    int size() const {
        return topIndex + 1;
    }

private:
    // 调整数组大小
    void resize(int newCapacity) {
        T* newData = new T[newCapacity];
        for (int i = 0; i <= topIndex; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }
};

int main() {
    ArrayStack<int> stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "Top element: " << stack.top() << std::endl;
    std::cout << "Stack size: " << stack.size() << std::endl;

    while (!stack.isEmpty()) {
        std::cout << "Popped: " << stack.pop() << std::endl;
    }

    return 0;
}